/**
 * Copyright 2010 - YangJiandong(chunquedong)
 * 
 * This file is part of ChunMap project
 * Licensed under the GNU LESSER GENERAL PUBLIC LICENSE(Version >=3)
 * 
 * ChunMap是开源软件。你可以自由复制、传播本项目的下载包文件，但必须保持其完整性。
 * 我们不用对使用中的风险及由此造成的损失承担任何责任。
 * 详细情况请见《ChunMap许可协议》。
 * 
 * 想了解更多有关ChunMap的信息，请访问http://code.google.com/p/chunmap/
 * 
 * 下面此段程序作者YangJianDong(chunquedong)
 * 最后修改时间2010.7.17
 */
package chunmap.data.index;

import java.util.ArrayList;
import java.util.List;

import chunmap.data.feature.Feature;
import chunmap.data.feature.FeatureSet;
import chunmap.data.feature.VisitAction;
import chunmap.data.feature.VisitFunc;
import chunmap.model.elem.Envelope;
/**
 * 四叉树索引
 * @author yangjiandong
 *
 */
public class QuartTree extends FeatureSet{
	QuartNode root;
    List<Feature> external;

    public QuartTree(Envelope origin)
    {
        root = new QuartNode(origin, 0, 6);
        external = new ArrayList<Feature>();
    }

    public void insert(Feature f)
    {
        if (root.getEnvelope().hasIntersect(f.getEnvelop()))
        {
            root.insert(f);
        }
        else
        {
            external.add(f);
        }
    }
    public boolean remove(Feature f)
    {
        if (root.getEnvelope().hasIntersect(f.getEnvelop()))
        {
            return root.remove(f);
        }
        else
        {
            return external.remove(f);
        }
    }

    public void search(Envelope envelope, VisitFunc filter)
    {
        if (root.getEnvelope().hasIntersect(envelope))
        {
            root.search(envelope, filter);
        }
        else
        {
            for (Feature f : external)
            {
                if (envelope.hasIntersect(f.getEnvelop()))
                {
                    if(!filter.execute(f))break;
                }
            }
        }
    }
    public void select(Envelope envelope, VisitAction filter)
    {
        if (root.getEnvelope().hasIntersect(envelope))
        {
            root.select(envelope, filter);
        }
        else
        {
            for (Feature f : external)
            {
                if (envelope.hasIntersect(f.getEnvelop()))
                {
                    filter.execute(f);
                }
            }
        }
    }

    public void find(VisitFunc filter)
    {
        root.find(filter);

        for (Feature f : external)
        {
            if(!filter.execute(f))break;
        }
    }
    public void each(VisitAction filter)
    {
        root.each(filter);

        for (Feature f : external)
        {
            filter.execute(f);
        }
    }
}
